1. Field of the Invention
The present invention relates to data transmission systems, and more particularly, to efficient processing of data within data transmission systems.
2. Description of the Related Art
Bi-directional digital data transmission systems are presently being developed for high-speed data communications. One standard for high-speed data communications over twisted-pair phone lines that has developed is known as Asymmetric Digital Subscriber Lines (ADSL). Another standard for high-speed data communications over twisted-pair phone lines that is presently proposed is known as Very High Speed Digital Subscriber Lines (VDSL).
The Alliance For Telecommunications Information Solutions (ATIS), which is a group accredited by the ANSI (American National Standard Institute) Standard Group, has finalized a discrete multi-tone based approach for the transmission of digital data over twisted-pair phone lines. The standard, known as ADSL, is intended primarily for transmitting video data and fast Internet access over ordinary telephone lines, although it may be used in a variety of other applications as well. The North American Standard is referred to as the ANSI T1.413 ADSL Standard (hereinafter ADSL standard), and is hereby incorporated by reference. Transmission rates under the ADSL standard are intended to facilitate the transmission of information at rates of up to 8 million bits per second (Mbits/s) over twisted-pair phone lines. The standardized system defines the use of a discrete multi-tone (DMT) system that uses 256 xe2x80x9ctonesxe2x80x9d or xe2x80x9csub-channelsxe2x80x9d that are each 4.3125 kHz wide in the forward (downstream) direction. In the context of a phone system, the downstream direction is defined as transmissions from the central office (typically owned by the telephone company) to a remote location that may be an end-user (i.e., a residence or business user). In other systems, the number of tones used may be widely varied.
The ADSL standard also defines the use of reverse transmissions at a data rate in the range of 16 to 800 Kbit/s. The reverse transmissions follow an upstream direction, as for example, from the remote location to the central office. Thus, the term ADSL comes from the fact that the data transmission rate is substantially higher in the downstream direction than in the upstream direction. This is particularly useful in systems that are intended to transmit video programming or video conferencing information to a remote location over telephone lines.
Because both downstream and upstream signals travel on the same pair of wires (that is, they are duplexed) they must be separated from each other in some way. The method of duplexing used in the ADSL standard is Frequency Division Duplexing (FDD) or echo canceling. In frequency division duplexed systems, the upstream and downstream signals occupy different frequency bands and are separated at the transmitters and receivers by filters. In echo cancel systems, the upstream and downstream signals occupy the same frequency bands and are separated by signal processing.
ANSI is producing another standard for subscriber line based transmission system, which is referred to as the VDSL standard. The VDSL standard is intended to facilitate transmission rates of at least about 6 Mbit/s and up to about 52 Mbit/s or greater in the downstream direction. Simultaneously, the Digital, Audio and Video Council (DAVIC) is working on a similar system, which is referred to as Fiber To The Curb (FTTC). The transmission medium from the xe2x80x9ccurbxe2x80x9d to the customer is standard unshielded twisted-pair (UTP) telephone lines.
A number of modulation schemes have been proposed for use in the VDSL and FTTC standards (hereinafter VDSL/FTTC). For example, some of the possible VDSL/FTTC modulation schemes include multi-carrier transmission schemes such as Discrete Multi-Tone modulation (DMT) or Discrete Wavelet Multi-Tone modulation (DWMT), as well as single carrier transmission schemes such as Quadrature Amplitude Modulation (QAM), Carrierless Amplitude and Phase modulation (CAP), Quadrature Phase Shift Keying (QPSK), or vestigial sideband modulation.
Most of the proposed VDSL/FTTC transmission schemes utilize frequency division duplexing of the upstream and downstream signals. One particular proposed VDSL/FTTC transmission scheme uses periodic synchronized upstream and downstream communication periods that do not overlap with one another. That is, the upstream and downstream communication periods for all of the wires that share a binder are synchronized. With this arrangement, all the very high speed transmissions within the same binder are synchronized and time division duplexed such that downstream communications are not transmitted at times that overlap with the transmission of upstream communications. This is also referred to as a (i.e. xe2x80x9cping pongxe2x80x9d) based data transmission scheme. Quiet periods, during which no data is transmitted in either direction, separate the upstream and downstream communication periods. When the synchronized time division duplexed (TDD) approach is used with DMT it is often referred to as synchronized DMT (SDMT).
A conventional transmitter for a multicarrier modulation system encodes data onto each of a plurality of frequency tones, and then modulates the frequency domain data supplied by the data symbol encoder with an Inverse Fast Fourier Transform (IFFT) unit to produce time domain signals to be transmitted. The time domain signals are then supplied to a digital-to-analog converter (DAC) where the analog signals are converted to digital signals. Thereafter, the digital signals are transmitted over a channel to one or more remote receivers.
A conventional remote receiver for a multicarrier modulation system. The remote receiver receives analog signals that have been transmitted over a channel by a transmitter. The received analog signals are supplied to an analog-to-digital converter (ADC) which produces digital signals. The digital signals are then supplied to a Fast Fourier Transform (FFT) unit that demodulates the digital signals while converting the digital signals from a time domain to a frequency domain. The demodulated digital signals are then supplied to a data symbol decoder to recover the data, or bits of data, transmitted on each of the carriers (frequency tones).
Transceivers (transmitters and receivers) implementing multicarrier modulation typically have significant processing and memory requirements. Typically, the processing requirements are carried out by digital signal processing. In one implementation the multicarrier modulation is performed by processing by a Fast Fourier Transform (FFT) processor or an Inverse Fast Fourier Transform (IFFT) processor. Often, the FFT/IFFT processor is implemented by a digital signal processor (DSP). It is known that FFT/IFFT computations require that the processing interact with a plurality of data points simultaneously. FFT/IFFT computations are thus complicated processing operations that simultaneously use a plurality of data points that are not sequential.
As a result, in conventional designs, the FFT/IFFT processor is required to have numerous ports which connect to numerous ports of a memory system. Further, the outputs of the FFT/IFFT processor was in most cases hardwired back the memory system where the output values were stored. In general, the conventional designs require that the FFT/IFFT processor be able to access any location in the memory system at any time, which required numerous ports and complex wiring. Thus, conventional designs are costly due to the numerous ports required as well as due to the complex hardwiring required.
One improvement to the conventional designs that has been done is to use xe2x80x9cin-placexe2x80x9d processing so as to make efficient use of the memory system. In-place processing efficiently uses available memory by storing computed values in the locations from which the data values (used to produce the computed values) were originally retrieved. In other words, by using an in-place processing technique, the overall size of the required system memory could be reduced. The reduced size of the memory made possible by in-place processing is an improvement to the cost of the design. However, the conventional designs even with in-place processing require a lot of memory ports and complicated hardwiring so that the data stored in the memory system could be accessed at any time and at any location. Additionally, to effectuate in-place processing, the results from the FFT/IFFT processor have to be returned to and stored in the memory system at the same memory location from which the data points leading to these results were originally fetched. The providing of these return paths to the memory system is problematic because the wiring requirements are very complicated. In the case of FFT/IFFT computations, the retrieval and storage to the memory system is difficult because the samples used are not used sequentially.
FIG. 1 illustrates a simplified block diagram of a conventional FFT/IFFT processing system 100. The conventional FFT/IFFT processing system 100 includes a processor 102, a memory system 104, a series of multiplexers 106, and a series of demultiplexers 108. The FFT processing system 100 is capable of performing in-place processing with respect to the memory system 104. However, as seen in FIG. 1, to provide the in-place processing each bank (BANK-0, BANK-1, BANK-2 and BANK-3) of the memory system 104 required multiple ports (in this example, four input ports and four output ports). In addition, the series of multiplexers 106 and the series of demultiplexers 108 together with the complicated wirings to and from each of the banks of the memory system 104 render the design of the conventional FFT/IFFT processing system 100 difficult to implement and consume a large amount of expensive die area on a semiconductor chip. The complicated wirings also have unpredictable delays which create timing difficulties.
Thus, there is a need for improved FFT/IFFT processing systems.
Broadly speaking, the invention relates to improved Fourier transform processing systems. The improved Fourier transform processing systems efficiently perform Fourier transform signal processing. In addition, the improved Fourier transform processing according to the invention performs address transformations to better and more efficiently use a memory system for in-place processing. The address transformations are provided by a generalized address translation algorithm that works for any size Fourier transform, in any radix, and with various memory architectures. The invention also relates to pipelined in-place processing.
The invention is particularly well suited for performing in-place processing in a data transmission system. Specifically, in a data transmission system that provides multicarrier modulation with IFFT operations or provides multicarrier demodulation with FFT operations, the in-place processing techniques of the invention are particularly advantageous. As an example, the invention is particularly useful for VDSL systems and DMT-based systems. Moreover, the invention can provide pipelined FFT/IFFT processing for high-speed operation. In the case of a transceiver for a data communications system, pipelined FFT/IFFT processing according to the invention can perform back-to-back FFT and IFFT operations which allows the FFT processing system to be efficiently shared by both the transmitter and receiver of the transceiver.
The invention can be implemented in numerous ways, including as an apparatus, system, method, or computer readable media. Several embodiments of the invention are discussed below.
As a data processing apparatus for a data transmission system, an embodiment of the invention includes: an input buffer that stores data samples for a symbol in a sequential manner; a first address transformer, the first address transformer operates to transform the sequential manner of the data samples into a non-sequential manner such that sequential addresses of the data samples for the symbol stored in the input buffer are transformed into non-sequential addresses; a memory system having n-banks of memory, the memory system stores the data samples from the input buffer to the n-bank memory system in accordance with the non-sequential addresses produced by the first address transformer; a processor, the processor operates to compute output samples for the symbol, with the processor producing n-output samples using one of the data samples in each of the n-banks of memory of the memory system; a second address transformer, the second address transformer operates to transform the non-sequential manner of the output samples into a sequential manner; and an output buffer, the output buffer stores the output data samples in the sequential manner.
As a method for in-place processing of data in a data transmission system, an embodiment of the invention includes the operations of: receiving a sequential stream of data samples; storing the sequential stream of the data samples into an n-bank memory system in a non-sequential manner in accordance with non-sequential addresses for the n-bank memory system determined based on a number of banks of the n-bank memory system and a radix of operation; concurrently retrieving n-samples from the n-bank memory system, one sample from each of the n-banks; processing the n-samples retrieved from the n-bank memory system to produce n-processed samples; and storing the n-processed samples into the n-bank memory system at the same respective locations as the n-samples were retrieved from the n-bank memory system.
As a memory system, an embodiment of the invention includes: an address transformer, the address transformer operates to transform a sequential manner of data samples into a non-sequential manner such that sequential addresses of the data samples for a set of data are transformed into non-sequential addresses; and n-banks of memory, the n-banks of memory store the data samples in accordance with the non-sequential addresses produced by the address transformer.
As a computer readable media containing program instructions for in-place processing of data in a data transmission system, an embodiment of the invention includes: first program instructions for receiving a sequential stream of data samples; and second program instructions for storing the sequential stream of the data samples into an n-bank memory system in a non-sequential manner in accordance with non-sequential addresses for the n-bank memory system determined based on a number of banks of the n-bank memory system and a radix of operation.
As a data processing apparatus for a data transmission system that uses a superframe for data transmissions, the superframe including at least one transmit frame, at least one receive frame and at least one quiet period, another embodiment of the invention includes: an input buffer that stores data samples for a symbol; a memory system, the memory system stores the data samples from the input buffer; control registers for defining the superframe for the data transmissions, thus allowing the apparatus to operate on various superframe formats; a processor, the processor operates to compute output samples for the superframe in accordance with the control registers; and an output buffer, the output buffer stores the output data samples.
The invention has numerous advantages. One advantage of the invention is that the memory system requires only one port per memory bank which results in a reduction in power and size of memory required, yet in-place computation is available. Another advantage of the invention is that the data samples are stored in the memory system in a non-sequential manner such that the data points can be easily fetched from the memory system in the order in which the FFT/IFFT processor requires them. Still another advantage of the invention is that complicated routing networks are not needed. Yet another advantage of the invention is that pipelined operation is facilitated such that multiple symbols can be concurrently processed, even a mixture of receive (FFT) and transmit (IFFT) symbols. Another advantage of the invention is that the superframe can be easily changed or boundary adjusted.
Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.